#include<iostream>
#include<queue>
#include<vector>
#include<utility>
using namespace std;

typedef pair<int, int> PII;
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};


//542.01矩阵
vector<vector<int>> updateMatrix(vector<vector<int>>& mat){
    int m = mat.size(), n = mat[0].size();
    //建立一个新的二维数组作为结果返回
    vector<vector<int>> ret(m, vector<int>(n));

    //创建一个队列
    queue<PII> q;

    //找到原始数组中的所有值为0的位置，并在新的数组中修改，同时入队
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            if(mat[i][j]==0){
                ret[i][j] = 0;
                q.push({i, j});
            }
            //将原始数组中非0的位置修改成-1
            else{
                ret[i][j] = -1;
            }
        }
    }

    while(!q.empty()){
        auto [a, b] = q.front();
        q.pop();

        for (int k = 0; k < 4; k++){
            int x = a + dx[k], y = b + dy[k];

            if(x>=0&&x<m&&y>=0&&y<n&&ret[x][y]==-1){
                //将相邻位置值为-1的入队，并修改成当前位置的值+1
                q.push({x, y});
                ret[x][y] = ret[a][b] + 1;
            }
        }
    }

    return ret;
}

//1020.飞地的数量
int numEnclaves(vector<vector<int>>& grid){
    //正难则反思想，找没有与边界相连的飞地数量难，可以反着来找与边界相连的飞地，剩下的就是最终要找的
    //可以使用深度搜索，也可以使用广度搜索，这里使用多源bfs

    int m = grid.size(), n = grid[0].size();

    //创建一个队列
    queue<PII> q;
    //遍历原始数组将边界上所有的1作为起始位置入队,并修改成2
    //第一列和最后一列
    for (int i = 0; i < m; i++){
        if(grid[i][0]==1){
            grid[i][0] = 2;
            q.push({i, 0});
        }
        if(grid[i][n-1]==1){
            grid[i][n - 1] = 2;
            q.push({i, n - 1});
        }
    }

    //第一行和最后一行
    for (int j = 0; j < n; j++){
        if(grid[0][j]==1){
            grid[0][j] = 2;
            q.push({0, j});
        }
        if(grid[m-1][j]==1){
            grid[m - 1][j] = 2;
            q.push({m - 1, j});
        }
    }

    while(!q.empty()){
        //获取队头元素
        auto [a, b] = q.front();
        q.pop();

        for (int k = 0; k < 4; k++){
            int x = a + dx[k], y = b + dy[k];
            if(x>=0&&x<m&&y>=0&&y<n&&grid[x][y]==1){
                //将所有与边界相连的1都修改成2
                grid[x][y] = 2;
                //入队
                q.push({x, y});
            }
        }
    }

    //遍历整个数组，遇到2说明是与边界相连的，遇到1说明是剩下的飞地，个数相加即可
    int ret=0;
    for(auto nums : grid){
        for(auto num : nums){
            if(num==1){
                ret++;
            }
        }
    }

    return ret;
}

//1765.地图中的最高点
vector<vector<int>> highestPeak(vector<vector<int>>& isWater){
    //首先理解题意，原始数组中，1表示水域，0表示陆地
    //返回一个新的数组，每个位置都表示高度，其中水域高度是0，其他相邻位置的高度与当前位置地高度插不超过1
    //既然要找某个位置的地最大高度，利用贪心地思想，每次相邻位置都比当前位置高1
    //本道题就转换成01矩阵

    int m = isWater.size(), n = isWater[0].size();
    //创建一个新的数组
    vector<vector<int>> ret(m, vector<int>(n));
    //创建一个队列
    queue<PII> q;

    //遍历原始数组，将值为1表示水域的下标入队，同时对应到新数组修改成高度0
    //值为0的表示陆地的下标，对应到新数组中修改成-1，
    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            if(isWater[i][j]==1){
                q.push({i, j});
                ret[i][j] = 0;
            }
            else{
                ret[i][j] = -1;
            }
        }
    }

    //循环出队
    while(!q.empty()){
        //获取队头下标，并出队
        auto [a,b]=q.front();
        q.pop();

        for (int k = 0; k < 4; k++){
            int x = a + dx[k], y = b + dy[k];
            if(x>=0&&x<m&&y>=0&&y<n&&ret[x][y]==-1){
                ret[x][y] = ret[a][b] + 1;
                q.push({x, y});
            }
        }
    }

    return ret;
}

//1162.地图分析
int maxDistance(vector<vector<int>>& grid){
    //还是和01矩阵一样，正难则反，反过来从陆地找海洋
    //原始数组中0表示海洋，1表示陆地

    int m = grid.size(), n = grid[0].size();

    vector<vector<int>> ret(m, vector<int>(n));
    queue<PII> q;

    for (int i = 0; i < m; i++){
        for (int j = 0; j < n; j++){
            if(grid[i][j]==1){
                q.push({i,j});
                ret[i][j] = 0;
            }
            else{
                ret[i][j] = -1;
            }
        }
    }

    if(q.size()==0||q.size()==m*n){
        return -1;
    }

    int maxnum = 0;
    while(!q.empty()){
        //获取队头下标，并出队
        auto [a,b]=q.front();
        q.pop();

        for (int k = 0; k < 4; k++){
            int x = a + dx[k], y = b + dy[k];
            if(x>=0&&x<m&&y>=0&&y<n&&ret[x][y]==-1){
                ret[x][y] = ret[a][b] + 1;
                maxnum = max(maxnum, ret[x][y]);
                q.push({x, y});
            }
        }
    }

    return maxnum;
}

int main(){
    vector<vector<int>> nums = {{1, 0, 0}, {0, 0, 0}, {0,0,0}};
    maxDistance(nums);
    return 0;
}